State Machines
Review what constitutes a state machine.
Implementing a fault-tolerant service using state machine replication requires us to be able to view our service in terms of state machines. Let's understand the characteristics of a state machine.
Core components of a state machine#
A state machine consists of two main components: state variables and commands.
State variables#
State variables of a state machine specify its state. These variables are any instances of data structures that provide details about the configuration of a server or information stored by them. They are like normal variables because they contain values.
Commands#
Commands of a state machine are programs, functions, or code that alter the state of the state machine. These commands can perform the following operations:
Update values of state variables
Give an output
A vital characteristic of these commands is that they are deterministic. We can assume that the program or code that implements these commands is deterministic. Another important characteristic of these commands is that their execution is atomic with other commands. These assumptions are necessary so that we can compare the result or output of the state machines with each other.
Point to ponder
Question
Since commands must be deterministic, doesn’t that exclude many use cases that require randomness?
Yes, use cases where randomness is required are excluded from state machines. For example, the generation of a random number is a non-deterministic computation. If such a task is done within the command of a process, it does not qualify as a state machine.
However, we can redesign our system so that non-deterministic computation occurs outside the state machine. We will demonstrate this later in the Example 3: Process control section of this lesson, where the operation of reading from a sensor (which is non-deterministic) takes place outside the state machine. In such cases, the non-deterministic operation’s output can be the state machine’s input.
Note: We will deliberately refrain from discussing how a command will be implemented or invoked to ensure that our model gives a general understanding. We will only talk about the steps involved in a command using pseudocode or plain English. We will describe state machines by only listing their state variables, commands, and the steps in those commands.
Complementary components#
Now that we know what makes up a state machine, we'll discuss components of the state machine approach that will help us understand the interaction to and from a state machine.
Clients and requests#
State machines have clients. A state machine's client can request to execute its commands. The client specifies the state machine, the command's name, and the information needed by the command in a request.
Output#
A request produces an output when the command specified in the request produces an output. The output of a request (or command) can be to storage or memory hardware, a controlling device that controls hardware, or other clients. We can also refer to this output as the output of the state machine that processes the request.
In the illustration above, the state machine has two state variables:
arr: An array that stores integers.L: Represents the length ofarr.
It has three commands:
arr(val): Placesvalat the smallest available index inarrthat is not in use. It returns-1if no index is available.update(val, ind): Updates the value at indexindinarrtoval. It returns1when done.read(val): Returns the value stored at indexindofarr.
The diagram shows that its clients send requests in the order insert(3), update(5, 2), and read(2). The “Output(s)” box shows outputs that the state machine returns after processing these requests. We can see that the first output is -1, so the insert(3) command could not find an index to place 3. The next output is 1, which indicates that update(5, 2) is executed successfully. And lastly, the output 5 is for the read(2) command.
We will briefly discuss how state machine process requests in the next lesson. In the following lessons, we will discuss this in more detail.
Request processing by state machines#
State machines process one request at a time. The order in which state machines process requests is consistent with potential causality. The two important assumptions that a state machine’s clients can make about the order in which it processes requests are as follows:
[
] A state machine processes requests by one of its clients in the order the client issued the requests. For example, a client issues requests to a state machine in the following order: request , then request , and then request . In this case, will process first, then , and then . [
] If a client makes a request to state machine that causes another client to make a request to , then will process before .
These two assumptions do not necessarily mean that
1 of 8
2 of 8
3 of 8
4 of 8
5 of 8
6 of 8
7 of 8
8 of 8
In the example above, the request
Point to ponder
Question
In the context of the above example, it is possible that two requests that arrive at a state machine might be concurrent (meaning there is no causality link between them). That might mean that the state machine can run them in any order. But doing so might break the consistency of replicas because one replica might order concurrent requests one way while the other does it differently. What are your thoughts?
We cannot allow different orders at different replicas. We need to totally order all the requests (including any concurrent requests with no causality link between them).
One possible solution might be that each replica orders concurrent requests by sending a client ID.
In practice, a leader gives a specific order to the requests and then forwards them to all the replicas. Later in this chapter, we’ll see how having a single leader and funneling all requests through it is a practical and common way to achieve atomic broadcast.
Semantic characterization of a state machine#
The defining characteristic of a state machine is that it gives a deterministic computation that reads and processes a stream of requests, and processing a request might or might not produce an output. In other words, given an initial state, only the sequence of requests processed by a state machine completely determines its output.
Point to ponder
Question
Since state machines process one request at a time, does that lead to performance limitations?
Yes, processing one request at a time can lead to performance limitations since we need to wait for a request to be processed before the next one so that the state machine can transition safely from one consistent state to the next.
With processing one request at a time, our state machine replicas process requests in the same order and end up in the same state while producing the same output. The state of all replicas remains consistent. With multiple requests being processed simultaneously, achieving this would take much work.
The potential loss of performance is the price we pay to get the fault tolerance via consistent state machine replicas. However if the performance is not acceptable for some applications, we might need to partition the state. In this case, each shard is managed by a different set of state machine replica groups. However, particular care must be taken when partitioning so that interaction between shards is either non-existent or minimal to achieve better performance.
Let's describe the components of the memory state machine. It has one state variable:
store: An array of sizen.
It has two commands:
read(loc): Returns (to the state machine's client) the value stored instoreat indexloc. Thelocindex is a required input ofread.write(loc, value): Updatesstoreat indexlocwithvalue. Bothlocandvalueare required inputs forwrite.
Example 2: A mutex#
This state machine ensures that only a single client can access a resource at a time.
The state machine described in the code widget uses two helper functions:
head(list_): Returns the first element of a listlist_.tail(list_): Returnslist_without it's first element.
Let's describe the components of the mutex state machine. It has two state variables:
user: Holds the current user's ID with access to the resource.waiting: Lists users awaiting access to the resource. The list contains the IDs of users.
It has two commands:
acquire(): Appends the current client's ID to thewaitinglist ifuseris not empty. Otherwise, it makes the currentclienttheuser.release(): Gives access to the client next in line (represented by the head of the waiting listhead(waiting)) if thewaitinglist is not empty. If the list is empty, it setsusertoNone(null).
Example 3: Process control#
Process control involves monitoring some values for some purpose. One purpose is to ensure that systems operate within safe limitations, for example, monitoring pipeline pressure in natural gas distribution. Sensors can monitor the value. In this example, we use a sensor to periodically check a value and send it to our state machine.
Let's describe the components of the process_control state machine. It has one state variable:
q: A real number.
It has one command:
adjust: Performs a functionFooonqandsensor_valand updates the value ofq. It then sends the new value ofqto theactuator.
Semantic characterization#
The process monitor is not a part of the state machine pc. By keeping monitor out of process_control, we ensure that process_control adheres to the semantic characterization property. Here is why. If we had kept a command in process_control that loops, reads from the sensor, writes to the actuator and then waits, then the output of process_control would not be entirely determined by a sequence of requests made to process_control because it would also depend on the time interval of delay. The process_control state machine would produce different outputs for different delay intervals. Therefore, by moving monitor out of the state machine, we remove the impact of the time delay d on the output of the state machine process_control.
What’s next?#
Now that we understand state machines and can model our services as a state machine, we’ll see how to replicate state machines for fault tolerance in the next lesson.
Introduction to State Machine Replication
Replication and Coordination of State Machines